package com.scqzy.shengchunqiang.sword2offer.day14;

/**
 * @Description: 剑指 Offer 13. 机器人的运动范围
 * @Author 盛春强
 * @Date 2021/8/21 20:14
 */
public class MovingCount {
    int m;
    int n;
    int k;

    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        this.m = m;
        this.n = n;
        this.k = k;
        return dfs(visited, 0, 0);
    }

    private int dfs(boolean[][] visited, int i, int j) {
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || (splitSum(i) + splitSum(j)) > k) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(visited, i + 1, j) + dfs(visited, i - 1, j) + dfs(visited, i, j + 1) + dfs(visited, i, j) + dfs(visited, i, j - 1);
    }

    private int splitSum(int i) {
        int sum = i%10;
        int tmp = i/10;
        while (tmp != 0) {
            sum+=tmp%10;
            tmp/=10;
        }
        return sum;
    }
}
